

# n = 100
#
# while n > 0 :
#
#     n = int(n/2)
#     print(n)
#
# def calc(n):
#     print(n)
#     n = int(n/2)
#     if n > 0 :
#         calc(n)
#
#     print(n)
#
# calc(100)

'''
练习题：

用递归实现二分查找，以从列表a = [1,3,4,6,8,9,11,15,17,19,21,22,25,29,33,38,69,107]查找指定的值。
'''

def bdf(arr,x):

    high = len(arr)

    mid  = high // 2

    if arr[mid] == x :
        return x
    elif arr[mid] > x :
        return bdf(arr[0:mid],x)
    else :
        return bdf(arr[mid+1:high],x)

a = [1,3,4,6,8,9,11,15,17,19,21,22,25,29,33,38,69,107]

x = None
while x != 0:
    x = int(input("输入您想查找的数："))
    if x > 200:
        print("Number is too large,end.")
        break
    elif x not in a :
        print("{}is not in list a.".format({x}))
    else:
        print(bdf(a,x),a.index(x))